/*
 * Copyright (C) 2012 The Guava Authors
 *
 * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except
 * in compliance with the License. You may obtain a copy of the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software distributed under the License
 * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
 * or implied. See the License for the specific language governing permissions and limitations under
 * the License.
 */

package com.google.common.collect;

import com.google.caliper.BeforeExperiment;
import com.google.caliper.Benchmark;
import com.google.caliper.Param;
import com.google.common.base.Optional;
import com.google.common.primitives.Ints;
import java.util.List;
import java.util.Random;

/**
 * Benchmarks for the {@code TreeTraverser} and optimized {@code BinaryTreeTraverser} operations on
 * binary trees.
 *
 * @author Louis Wasserman
 */
public class BinaryTreeTraverserBenchmark {
    private static class BinaryNode {
        final int x;
        final Optional<BinaryNode> left;
        final Optional<BinaryNode> right;

        BinaryNode(int x, Optional<BinaryNode> left, Optional<BinaryNode> right) {
            this.x = x;
            this.left = left;
            this.right = right;
        }
    }

    enum Topology {
        BALANCED {
            @Override
            Optional<BinaryNode> createTree(int size, Random rng) {
                if (size == 0) {
                    return Optional.absent();
                } else {
                    int leftChildSize = (size - 1) / 2;
                    int rightChildSize = size - 1 - leftChildSize;
                    return Optional.of(new BinaryNode(rng.nextInt(), createTree(leftChildSize, rng),
                            createTree(rightChildSize, rng)));
                }
            }
        },
        ALL_LEFT {
            @Override
            Optional<BinaryNode> createTree(int size, Random rng) {
                Optional<BinaryNode> root = Optional.absent();
                for (int i = 0; i < size; i++) {
                    root = Optional.of(new BinaryNode(rng.nextInt(), root, Optional.<BinaryNode>absent()));
                }
                return root;
            }
        },
        ALL_RIGHT {
            @Override
            Optional<BinaryNode> createTree(int size, Random rng) {
                Optional<BinaryNode> root = Optional.absent();
                for (int i = 0; i < size; i++) {
                    root = Optional.of(new BinaryNode(rng.nextInt(), Optional.<BinaryNode>absent(), root));
                }
                return root;
            }
        },
        RANDOM {
            /**
             * Generates a tree with topology selected uniformly at random from the topologies of
             * binary trees of the specified size.
             */
            @Override
            Optional<BinaryNode> createTree(int size, Random rng) {
                int[] keys = new int[size];
                for (int i = 0; i < size; i++) {
                    keys[i] = rng.nextInt();
                }
                return createTreap(Ints.asList(keys));
            }

            // See http://en.wikipedia.org/wiki/Treap for details on the algorithm.
            private Optional<BinaryNode> createTreap(List<Integer> keys) {
                if (keys.isEmpty()) {
                    return Optional.absent();
                }
                int minIndex = 0;
                for (int i = 1; i < keys.size(); i++) {
                    if (keys.get(i) < keys.get(minIndex)) {
                        minIndex = i;
                    }
                }
                Optional<BinaryNode> leftChild = createTreap(keys.subList(0, minIndex));
                Optional<BinaryNode> rightChild = createTreap(keys.subList(minIndex + 1, keys.size()));
                return Optional.of(new BinaryNode(keys.get(minIndex), leftChild, rightChild));
            }
        };

        abstract Optional<BinaryNode> createTree(int size, Random rng);
    }

    private static final BinaryTreeTraverser<BinaryNode> BINARY_VIEWER = new BinaryTreeTraverser<BinaryNode>() {

        @Override
        public Optional<BinaryNode> leftChild(BinaryNode node) {
            return node.left;
        }

        @Override
        public Optional<BinaryNode> rightChild(BinaryNode node) {
            return node.right;
        }
    };

    private static final TreeTraverser<BinaryNode> VIEWER = new TreeTraverser<BinaryNode>() {
        @Override
        public Iterable<BinaryNode> children(BinaryNode root) {
            return BINARY_VIEWER.children(root);
        }
    };

    enum Traversal {
        PRE_ORDER {
            @Override
            <T> Iterable<T> view(T root, TreeTraverser<T> viewer) {
                return viewer.preOrderTraversal(root);
            }
        },
        POST_ORDER {
            @Override
            <T> Iterable<T> view(T root, TreeTraverser<T> viewer) {
                return viewer.postOrderTraversal(root);
            }
        },
        BREADTH_FIRST {
            @Override
            <T> Iterable<T> view(T root, TreeTraverser<T> viewer) {
                return viewer.breadthFirstTraversal(root);
            }
        };

        abstract <T> Iterable<T> view(T root, TreeTraverser<T> viewer);
    }

    private Iterable<BinaryNode> view;

    @Param
    Topology topology;

    @Param({"1", "100", "10000", "1000000"})
    int size;

    @Param
    Traversal traversal;

    @Param
    boolean useBinaryTraverser;

    @Param({"1234"})
    SpecialRandom rng;

    @BeforeExperiment
    void setUp() {
        this.view = traversal.view(topology.createTree(size, rng).get(), useBinaryTraverser ? BINARY_VIEWER : VIEWER);
    }

    @Benchmark
    int traversal(int reps) {
        int tmp = 0;

        for (int i = 0; i < reps; i++) {
            for (BinaryNode node : view) {
                tmp += node.x;
            }
        }
        return tmp;
    }
}
